/*
Date:20210504 21:46PM
key:完全没看答案，折磨我好几个小时，首先最大矩形的操作行不通，如下
    10
    11
    11
    11 会输出竖着的最大矩形

    其次思考动态规划。每一个dp[i][j]都是以当前mat[i][j]为右下角的最大正方形的面积
    因此如果mat[i][j]=1&&行左和行上在sqrt(dp[i-1][j-1])的长度上都是1，就可以成为一个新的大正方形。

    但是如果达不到，在len范围内，相当于借助以mat[i-1][j-1]为右下角的三角形的部分，就看行左和列上谁的连续1走得更短，以这个距离平方得到当前位置的dp[i][j] 如
    1101
    1110
    0111
    边界要相当注意！
    横的每个两次，列有行次，应该是O(n^2)

    看了答案解法，实际上我这里也是三个边在看谁最小，因为其余两个大的边形成的正方形一定能覆盖小的。
*/
class Solution {
public:

    int checkl(vector<vector<char>>& matrix,int i1,int j1,int len)
    {
        int i;
        for(i=0;i<=len;i++)
        {
            if(matrix[i1-i][j1]=='0'){return i;}
        }
        // for(int i=0;i<=len;i++)
        // {
        //     if(matrix[i1][j1-i]=='0'){return 0;}
        // }
        return i;
    }

    int checkr(vector<vector<char>>& matrix,int i1,int j1,int len)
    {
int i;
        for(i=0;i<=len;i++)
        {
            if(matrix[i1][j1-i]=='0'){return i;}
        }
        return i;
    }
    int maximalSquare(vector<vector<char>>& matrix) 
    {
        vector<vector<int>> dp;
        dp.resize(matrix.size());
        for(int i=0;i<matrix.size();i++)
        {
            dp[i].resize(matrix[0].size());

        }
        for(int i=0;i<matrix.size();i++)
        {
            dp[i][0]=matrix[i][0]-48;
        }
        for(int i=0;i<matrix[0].size();i++)
        {
            dp[0][i]=matrix[0][i]-48;
        }
        int Max=0;
        for(int i=1;i<matrix.size();i++)
        {
            for(int j=1;j<matrix[0].size();j++)
            {
                if(dp[i-1][j-1]!=0)
                {
                    if(matrix[i][j]=='0'){dp[i][j]=matrix[i][j]-48;continue;}
                    int len=sqrt(dp[i-1][j-1]);
                    //int min1=min(checkl(matrix,i,j,len),min(checkr(matrix,i,j,len),len));
                    int min1=min(checkl(matrix,i,j,len),(checkr(matrix,i,j,len)));
                    if(min1>len)
                        {dp[i][j]=(len+1)*(len+1);
                        //cout<<dp[i][j];
                    }
                    else{dp[i][j]=(min1)*(min1);}
                }
                else{dp[i][j]=matrix[i][j]-48;}
            }
        }
        //
                for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                //cout<<dp[i][j];
                Max=max(Max,dp[i][j]);
            }
            //cout<<"\n";
        }
        return Max;
    }
};